今天的題單：

• Longest Substring Without Repeating Characters

• 3Sum

3. Longest Substring Without Repeating Characters

思路: 設定 head 和 tail 分別指向目前檢查 substring 頭尾。從第一個字開始往後看，每看一個字檢查目前 head 和 tail 指出的這段 substring 內有沒有相同的字，有的話就把 head 往後移到重複的字的下一個字符。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int head = 0;
        int tail = 1;
        int max_len = 0;

        if (s.length() == 0) // string is empty
            return 0;

        while (tail < s.length()) {
            int curr = head;
            while (curr < tail) {
                if (s[curr] == s[tail])
                    break;
                curr++;
            }
            if (curr != tail) {    // repeat 
                max_len = max(max_len, tail-head);
                head = curr + 1;
            }

            tail++;
        }

        max_len = max(max_len, tail-head);

        return max_len;
    }
};

15. 3Sum

給一段數字陣列，找出三個不同位置的數字組合(array[i], array[j], array[k] , i != j, i != k, j != k)相加是 0 的所有組合。 組合不能重複。

examples

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = [0,0,0,0]
Output: [[0,0,0]]

思路﹔看看固定 array[i] 以外有哪兩個數字和 array[i] 相加可以等於 0。

這個方法要先將 array 做排序。使用三個指標 i, j, k ，固定 i ，j 指向 i 的下一個數字(除了 i 以外最小值)，k 指向最後一個數字 (最大值)，j 和 k 逐漸往中間逼近看有沒有可能三個數字相加等於 0。i 和 j 如果遇到看過的數字要跳掉不然會記到重複的組合。
暴力解需要 O(n^3) time，這個方法可以降成 O(n^2) time。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int i = 0;
        vector<vector<int>> solutions;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size()-2; i++) {
            int j = i + 1;
            int k = nums.size() - 1;
            
            if (i >= 1 && nums[i] == nums[i-1]) continue;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    if (!(i != j-1 && nums[j] == nums[j-1])) {
                        vector<int> sol = {nums[i], nums[j], nums[k]};
                        solutions.push_back(sol);
                    }
                    j++;
                    k--;
                } else if (nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }

        return solutions;
    }

    
};